The invention relates generally to a method for searching a set of elements to identify one which closely matches a reference. More specifically, the invention relates to a vector quantizer which utilizes such a method to compress video data.
Numerous fields of endeavor make use of vector processing. One newly emerging application is data compression. The preferred embodiment of the invention will be described with particular reference to compression of image signals, though such an illustration is not a limitation on its scope.
A quantizer is a device which represents one signal which can take on a large number of values by another signal which can take on only a limited number of values. A four bit analog-to-digital converter, for example, represents the value of a continuously varying (i.e., analog) signal by a digital signal which can have only one of sixteen values. Scalar quantizers operate on signals having a single degree of freedom, such as an analog-to-digital converter operating on a voltage signal. Vector quantizers operate on signals having multiple degrees of freedom as will be discussed more fully below.
A vector quantizer for compressing video images conceptually divides the image into numerous small areas called pixels (a term formed from the words "picture" and "element"). Pixels are sufficiently small that the intensity of the image is approximately constant across the pixel area. For example, a black and white image of a house might be divided into a grid of 600 rows and 600 pixels per row. Each pixel would be like a small dot in the image. A group of pixels together would form a vector which can be thought of as a small subimage. For example a 6.times.6 square patch of pixels forms a vector which may be a portion of a shadow, or part of the roof line against a light background. Vectors formed from an image shall be called image vectors. The circuit of the present invention operates on vectors which, for the illustrated example, are image vectors. In general, any source of vector signals may be used, and vectors which are subject to quantization are more generally referred to as input vectors.
While a black and white image serves as an example here, vectors might also be formed from red, green, or blue levels from a color image. They might also be formed from Y,I and Q components of a color image, or from transform coefficients of an image signal on which a Hadamard, Fourier, or other transform has operated.
Numerous methods exist for manipulating an image to form image vectors. For example, a television camera might generate an analog video signal in a raster scan format having 600 scan lines per frame. An analog-to-digital converter could then digitize the video signal at a sampling rate of 600 samples per scan line. Digital signal processing equipment can then store the digital samples, and group them into vectors. The process of digitizing an analog video signal is a form of scalar quantization which is similar to but distinct from methods of vector quantization. The discussion which follows assumes that one of many methods well known in the art of signal processing can be used to produce digital image signals.
Before quantizing an image, a vector quantizer stores a set of "codebook" vectors in memory. Codebook vectors are vectors which are chosen to be representative of commonly found image vectors. For example, one codebook vector might be a 6.times.6 pixel solid black patch. Another codebook vector might have all white pixels in the top three rows, and all black pixels in the bottom three rows. Yet another codebook vector might have a gradient made up of white pixels in the top row, black pixels in the bottom row, and four rows in between having shades of grey which go from light to dark. The quantizer stores a sufficient variety of codebook vectors so that at least one closely matches each of the many vectors that might be found in the full image.
Each codebook vector is assigned a unique identification code. The solid black patch, for example, might be assigned ID code #1. The codebook vector having white pixels in the top half and black pixels in the bottom half might be assigned ID code #2, and so on for hundreds or thousands of codebook vectors. The set of all codebook vectors is called a codebook.
When quantizing a full image, a vector quantizer divides the full image into a series of image vectors. For each image vector, the vector quantizer identifies one closely matching codebook vector. The vector quantizer then generates a new signal made up of the series of the identification codes of the selected codebook entries. For the example of a full image of a house, the vector quantizer would divide the full image into numerous image vectors. The quantizer might then replace image vectors from shadow areas with ID code #1 (the solid black patch), and it might replace roof line image vectors with ID code #2 (white in the top half and black in the bottom half).
Regeneration of the full image can be accomplished by a device which has the complete codebook stored in memory. The device regenerates the image signal by replacing each ID code in the quantized signal with its corresponding codebook vector. The process is similar to "painting by the numbers." The regenerated image differs from the original image, because codebook entries do not precisely match the original image vectors. The difference is called distortion. Increasing the number of codebook entries decreases distortion.
In mathematical terms, a vector quantizer is a device which maps vectors from a vector space onto a finite set. A pixel from a black and white image is a scalar, because the pixel has only one degree of freedom: intensity. A 6.times.6 square patch of pixels is a vector, because the square patch has numerous degrees of freedom: the intensities of each of the thirty six pixels. The set of all possible image vectors forms a vector space.
Conceptually, the vector space can be partitioned into a finite number of regions. One vector from each region can be designated as a codebook vector for that region. All possible image vectors exist somewhere in the vector space. Each possible image vector thus lies within one of the regions. In fact, multiple image vectors might occupy the same region. For all image vectors in a given region, the vector quantizer replaces the image vector with an identification code for that region. The vector quantizer thus maps all vectors of the vector space onto a set of identification codes. When regenerating the image, each identification code is replaced with the codebook vector for the corresponding region.
Vector quantizers are developing as useful devices for compressing data. A compressor, as the term is used here, is a device which represents one signal by a second signal from which the original can be derived, but which requires the transmission or recording of less information than the original signal. For example, digitally transmitting a full image ordinarily requires transmitting the intensities of each pixel of each row of the full image. A vector quantizer instead transmits an ID code for each image vector.
A vector quantizer sends fewer bits than would otherwise be sent, because one ID code is a smaller number of bits than all the pixel intensities of the image vector. Suppose, for example, that each pixel intensity in an image is represented by an eight bit binary number (eight bits allows definition of 256 levels of intensity for each pixel). Suppose also that image vectors are made up of thirty six pixels. A vector could thus be represented by 288 bits (8 bits/pixel times 36 pixels equals 288 bits). In addition, suppose that a codebook contains 1024 entries. (Experience has shown that reasonable image quality can be achieved with a codebook of 1024 vectors.) Each of the 1024 entries can by uniquely designated by a ten bit identification code. By replacing each image vector with identification code of a codebook vector, a vector quantizer replaces 288 bits with 10 bits.
Some vector quantizers utilize computers to store codebook vectors in memory. They then employ some form of software program to search the memory for a match between an image vector and a codebook vector. Identifying the codebook vector which most closely matches an image vector requires a significant number of computational steps. It is known that computing devices perform mathematical operations in steps. The binary sum of two numbers may, for example require one or more steps. A multiplication of two numbers may require a greater number of steps. Computing the square root of a number may require an even greater number. The number of computational steps needed to match an input vector to a codebook vector is thought to increase linearly with the number of codebook entries. This has created limitations with such quantizers. The lengthy time required to perform the computational steps forces designers to sacrifice image quality for speed, because they must use small codebooks, or vectors of small dimension. Alternatively some designers resort to complicated signal processing in advance of vector quantization in order to reduce the amount of information which must be quantized.
A full codebook search is an example of one straightforward method for selecting the best match between an image vector and the codebook entries. The vector quantizer sequentially compares an input image vector to each and every codebook vector. The vector quantizer computes a measure of distortion for each codebook vector and selects the one having the smallest distortion. A full codebook search ensures selection of the best match (a property called optimality), but involves the maximum number of computational steps. The article by Y. Linde, A. Buzo and R. Gray entitled "An Algorithm for Vector Quantizer Design," IEEE Transactions on Communications, Vol. Com-28, No. 1 (Jan. 1980) describes the full codebook search and the computational steps involved in such a search.
A technique known as a branching search reduces the number of codebook entries which must be evaluated, but does not necessarily identify the best match. Murakami U.S. Pat. Nos. 4,558,350 and 4,560,977 disclose vector quantizers using branching searches. The article by R. Gray and Y. Linde entitled "Vector Quantizers and Predictive Quantizers for Gauss-Markov Sources," IEEE Transactions on Communications, Vol. Com-30, No. 2 (Feb. 1982) describes the branching tree search and some of its shortcomings.
The vector quantizer described in Lindsey U.S. Pat. No. 4,727,354 reduces the number of computational steps required to match an input to a codebook vector by eliminating the computation of distortion. The distortion between each codebook vector and all possible input vectors is calculated in advance and stored in memory. Such a method requires large amounts of memory relative to other methods.